1. Field of the Invention
The present invention relates to electronics, specifically the proactive caching of electronic information for quick delivery to users.
2. Description of the Related Art
Internet Protocol Television
IPTV (Internet Protocol Television) is a protocol for the delivery of digital information over a network infrastructure using the Internet Protocol (IP). IPTV does not follow the typical unicast model of Internet communications. In the unicast model, a single requesting party requests a particular piece of information (e.g., an HTML page), and a serving party serves up that specific information in response to the request. Both requesting party and serving party possess unique IP addresses which allow the Internet hardware and software that connects those two parties (e.g., routers, switches, hubs, etc.) to route information between those two and only those two parties. Thus, going to www.youtube.com, selecting and watching a particular video is unicast streaming video, not IPTV.
In contrast, IPTV is based on a multicast model similar to broadcast technologies such as radio and TV. Like a TV transmitter or DBS satellite, an IPTV source (such as an IPTV server) continuously outputs one or more channels of TV programming as IP streams, and does so according to a pre-defined schedule, instead of serving up specific information in response to a request. Furthermore, intermediate routers and other Internet hardware do not deliver the IPTV channel streams to specific IP addresses, but instead multicast those streams to one or more multicast groups on a more-or-less continuous basis.
Although IPTV's delivery mechanism differs from delivery mechanism of traditional TV, the user interface is similar. IGMP streams are presented as numbered channels. The set of all the numbered channels is a lineup. Users can switch to a channel via the same methods present in traditional TV, e.g., entering a channel number directly (i.e., jumping), selecting a channel from an Electronic Program Guide (EPG), surfing (i.e., walking to) an adjacent channel by hitting a channel increment or decrement button, etc. Adjacent channels can be but need not be represented by consecutive channel numbers.
Users wishing to view a particular IPTV channel typically must join a multicast group to receive the IPTV channel, and leave the multicast group when they wish to view another IPTV channel. Internet Group Management Protocol (IGMP) is a protocol commonly used in IPTV systems for the management of multicast groups. IGMP performs group join/leave operations, and IPTV operators typically record information about these operations in the form of an IGMP log file. An IGMP log typically comprises any number of entries, where each entry represents an individual join/leave activity. IGMP log entries are typically in the form <user, time, channel (i.e., group), join/leave>.
IGMP takes a certain amount of time to perform a join/leave operation. Additionally, in IPTV, joining a multicast group often entails consulting an authentication server to verify that a subscriber is in fact entitled to join the requested multicast group (i.e., view the IPTV channel), an additional operation which takes a further amount of time.
Telephone companies (telcos), among others, deploy IPTV technology in order to deliver television programming to subscribers over digital subscriber line (DSL) infrastructure. FIG. 1 is a block diagram of a typical IPTV network 100. At the topmost level are Super Head-End Offices (SHO) 102. SHOs are computer facilities that acquire and aggregate content from multiple national content providers (e.g., Viacom, Time Warner, etc.). A typical telco will have two to four SHOs for the entire U.S.
SHOs 102 distribute the aggregated content to Video Head-End Offices (VHO) 106 over high-capacity core network 104. A typical aggregated-content stream will be a 10 gigabit-per-second (Gb/s) signal. A typical telco will have approximately forty VHOs, with each one located in major metropolitan areas. VHOs are typically responsible for the acquisition and insertion of local programming and advertising. A VHO might contain multiple distribution servers (D-Servers) 108 that buffer current video streams at the video source for speeding up user channel-change operations.
VHOs 106 relay content to Central Offices (CO) 110 over high-capacity metro ring 108. In a typical implementation, there are approximately 5-25 COs per VHO, and each CO is responsible for serving approximately 25,000 households.
COs 110 relay content to Digital Subscriber Line Access Modules (DSLAM) 112 over 1 Gb/s connections. In a typical implementation, there are no more than 80 DSLAMs per CO, and each DSLAM is responsible for serving approximately 400 households.
DSLAMs 112 relay content to end-user Set-Top Boxes (STB) 114 over 20 megabit-per-second (Mb/s) DSL connections. STBs connect to user television sets. In a typical implementation, there are two STBs per household, and thus each DSLAM is responsible for serving content to 800 STBs.
The content streamed over an IPTV network is typically video content encoded into digital data using a video encoder program which employs various data compression methods. A widely-used standard for video encoding is the Motion Pictures Expert Group (MPEG) standard. MPEG encoding achieves significant reductions in the size of the resulting digital data through, inter alia, the elimination of redundant inter-frame data. Most video content consists of a linear sequence of images, or frames. For example, films are typically recorded at 25-30 frames per second. Often, much of the information contained in adjacent frames is redundant, i.e., the picture element at coordinates x, y in frame N is approximately the same value as the picture element at those same coordinates in frame N+1 or N−1. Thus, instead of always sending complete frames, MPEG sends a complete frame (also known as an intra-coded frame or I-frame), and then sends one or more frames (known as P-frames and B-frames) which contain only the differences from immediately preceding or following frames.
At the receiving end, a typical MPEG decoder requires an I-frame before it can begin outputting a viewable signal. The number of I-frames encoded per second is specified by the entity performing the encoding, and typically ranges from one I-frame every half-second to one I-frame every second. Thus, if an IPTV channel has been encoded with an I-frame every second, it is possible that a subscriber selecting that channel may have to wait a second for the MPEG decoder to begin outputting a viewable signal.
Furthermore, the viewable output signal of an MPEG decoder is typically buffered so that intermittent and brief interruptions in the input signal of the decoder do not result in interruptions in the viewable signal. Typically, this buffer must be filled with viewable signal before the buffer begins transmitting viewable signal. Hence, there is a delay between when the buffer first receives viewable signal, and when that buffer begins outputting viewable signal.
The Problem of Channel-Change Latency in IPTV
Channel-change latency is the total time from the moment a viewing user selects a new/different channel, to the moment when that new channel's output appears on the screen. In IPTV systems, channel-change latency becomes a major challenge for providing satisfactory quality of experience to broadcast TV users. Viewers of analog, cable, and satellite TV have become accustomed to extremely low (e.g., sub-second) channel-change latency times, while IPTV channel-change latency is significantly larger (e.g., three seconds) due to IGMP join/leave operations, decoding the first available I-frame, and filling of the user buffer, among others.
Typically, obtaining and decoding the first available I-frame is the largest component of IPTV channel-change latency. One solution to this problem is to allow network elements close to the user to cache the most recent x seconds of channel programming as independently decodable frames, i.e., a rolling window cache of fully decoded video. When the user does selects a cached channel, the cached (independently decodable) frames are sent to the user video buffer while the STB performs the IGMP operations, receives the first I-frame, and fills its buffer.
Ideally, all channels would be cached, insuring lowest channel-change latency regardless of the channel chosen However, bandwidth and other resource constraints often make the caching of all channels in a lineup impractical or wasteful. Thus, a typical implementation of a caching solution requires the operator to decide which channels are to be cached, and which are not. That decision directly impacts the effectiveness of channel caching on reducing channel-change latency, and the bandwidth consumption due to channel caching. Complicating this decision is the diversity and dynamics of user interests and TV program lineup settings.
Popularity is one method for selecting which channels are to be cached. If VC is the number of viewers that viewed a channel C during time T, and MC is the average number of minutes viewers VC viewed channel C, then popularity PC of channel C may be represented by VC×MC. Those channels with the largest PC values are cached. An alternative method for determining PC is to use third-party polling data, e.g., Nielsen.
However, just because a channel is unpopular does not necessarily mean it is not visited often. Users often walk through the channels adjacent to the currently watched channel for various reasons, e.g., to go to a destination channel not far from the current channel, to see what's on nearby channels during a commercial break, etc. In contrast, a user will often jump directly from one popular channel to another if the distance between those two channels is sufficiently large. Thus, there may be unpopular channels (i.e., channels with low PC values) that are nevertheless visited often (i.e., have high IGMP join counts) because they are close to a popular channel.